#include "Format.h"

class RadixSort {
public:
    RadixSort();

    RadixSort(int *arr, int num) {
        RadixSort();
        this->sort(arr, num);
        Format::format(arr, num);
    }

    ~RadixSort();

private:
    int maxbit(int data[], int num);
    void sort(int data[], int num);
};





RadixSort::RadixSort() {
}

RadixSort::~RadixSort() {
}

int RadixSort::maxbit(int *arr, int num) //���������������ݵ����λ��
{
    int moveCount = 0, compareCount = 0;
    int d = 1; //��������λ��
    int p = 10;
    moveCount += 2;
    for (int i = 0; i < num; ++i) {
        while (arr[i] >= p) {
            p *= 10;
            ++d;
            moveCount += 2;
        }
        moveCount++;
        compareCount++;
    }
    arr[num] += moveCount;
    arr[num + 1] += compareCount;
    return d;
}

void RadixSort::sort(int *arr, int num) //��������
{
    int moveCount = 0, compareCount = 0;
    int d = maxbit(arr, num);
    int *tmp = new int[num];
    int *count = new int[10]; //������
    int i, j, k;
    int radix = 1;
    moveCount += 5;
    for (i = 1; i <= d; i++) //����d������
    {
        moveCount++;
        compareCount++;
        for (j = 0; j < 10; j++) {
            count[j] = 0; //ÿ�η���ǰ��ռ�����
            moveCount += 2;
            compareCount++;
        }
        for (j = 0; j < num; j++) {
            k = (arr[j] / radix) % 10; //ͳ��ÿ��Ͱ�еļ�¼��
            count[k]++;
            moveCount += 3;
            compareCount++;
        }
        for (j = 1; j < 10; j++) {
            count[j] = count[j - 1] + count[j]; //��tmp�е�λ�����η����ÿ��Ͱ
            moveCount += 2;
            compareCount++;

        }
        for (j = num - 1; j >= 0; j--) //������Ͱ�м�¼�����ռ���tmp��
        {
            k = (arr[j] / radix) % 10;
            tmp[count[k] - 1] = arr[j];
            count[k]--;
            moveCount += 4;
        }
        for (j = 0; j < num; j++) //����ʱ��������ݸ��Ƶ�arr��
        {
            arr[j] = tmp[j];
            moveCount += 2;
        }
        radix = radix * 10;
        moveCount++;
    }
    delete[]tmp;
    delete[]count;
    arr[num] += moveCount;
    arr[num + 1] += compareCount;
}